In this paper we show that sufficient multi-partite quantum entanglementhelps in fair and unbiased election of a leader in a distributed network ofprocessors with only linear classical communication complexity. We show that atotal of $O(\log n)$ distinct multi-partite maximally entanglement sets (ebits)are capable of supporting such a protocol in the presence of nodes that may lieand thus be biased. Here, $n$ is the number of nodes in the network. We alsodemonstrate the difficulty of performing unbiased and fair election of a leaderwith linear classical communication complexity in the absence of quantumentanglement even if all nodes have perfect random bit generators. We show thatthe presence of a sufficient number $O(n/\log n)$ of biased agents leads to anon-zero limiting probability of biased election of the leader, whereas, thepresence of a smaller number $O(\log n)$ of biased agents matters little. Wedefine two new related complexity classes motivated by the our leader electionproblem and discuss a few open questions.
展开▼
